package leetcode.code1851;

/**
 * 线段树 <br>
 * 第34 / 42 个通过测试用例 超时
 */
public class Solution1 extends Solution1851 {
	int MIN = 1;
	int MAX = (int) 1e7;//

	class Node {
		int L, M, R;
		Node Left, Right;
		Integer minRange;
		Integer cache;

		public Node(int l, int r) {
			this.L = l;
			this.R = r;
			this.M = ((r - l) >> 1) + l;
			this.minRange = null;
			this.cache = null;
		}

		public Node getLeft() {
			if (this.Left == null) {
				this.Left = new Node(L, M);
			}
			return this.Left;
		}

		public Node getRight() {
			if (this.Right == null) {
				this.Right = new Node(M + 1, R);
			}
			return this.Right;
		}

		public void update(int l, int r, int range) {
			if (l <= this.L && this.R <= r) {
				if (this.minRange == null) {
					this.minRange = range;
					this.cache = range;
				} else if (range < this.minRange) {
					this.minRange = range;
					this.cache = range;
				}
				return;
			}
			pushDown();
			if (r <= this.M) {
				this.getLeft().update(l, r, range);
			} else if (l > this.M) {
				this.getRight().update(l, r, range);
			} else {
				this.getLeft().update(l, M, range);
				this.getRight().update(M + 1, r, range);
			}
			this.minRange = null;
		}

		public int query(int l) {
			if (l <= this.L && this.R <= l && this.minRange != null) {
				return this.minRange;
			}
			if (this.L == this.R && this.minRange == null) {
				return -1;
			}
			pushDown();
			int ans = -1;
			if (l <= this.M) {
				ans = this.getLeft().query(l);
			} else if (l > this.M) {
				ans = this.getRight().query(l);
			}
			return ans;
		}

		private void pushDown() {
			if (this.cache != null) {
				this.getLeft().cache = this.getLeft().cache == null ? cache : Math.min(this.getLeft().cache, cache);
				this.getRight().cache = this.getRight().cache == null ? cache : Math.min(this.getRight().cache, cache);
				this.getLeft().minRange = this.getLeft().minRange == null ? cache
						: Math.min(this.getLeft().minRange, cache);
				this.getRight().minRange = this.getRight().minRange == null ? cache
						: Math.min(this.getRight().minRange, cache);
				this.cache = null;
			}
		}

	}

	@Override
	public int[] minInterval(int[][] intervals, int[] queries) {
		Node root = new Node(MIN, MAX);
		for (int[] interval : intervals) {
			root.update(interval[0], interval[1], interval[1] - interval[0] + 1);
		}
		int len = queries.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			ans[i] = root.query(queries[i]);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
	}

}
